// https://www.lintcode.cn/problem/output-contest-matches/description?_from=ladder&&fromId=86
// 也不要想太复杂

class Solution {
public:
    /**
     * @param n: a integer, denote the number of teams
     * @return: a string
     */
    //递归
    // vector<string> solve(vector<string> tmp)
    // {
    //     vector<string> result;
    //     for (int i = 0; i < tmp.size() / 2; ++i)
    //     {
    //         result.push_back('(' + tmp[i] + ',' + tmp[tmp.size() - i - 1] + ')');
    //     }
    //     return result;
    // }
    // string findContestMatch(int n) {
    //     vector<string> s;
    //     vector<string> result;
    //     for (int i = 1; i <= n; ++i)
    //     {
    //         s.push_back(to_string(i));
    //     }
    //     while (result.size() != 1)
    //     {
    //         result = solve(s);
    //         s = result;
    //     }
    //     return result[0];
    // }
    
    // 非递归
    string findContestMatch(int n) {
        vector<string> s;
        for (int i = 1; i <= n; ++i)
        {
            s.push_back(to_string(i));
        }
        while (n > 1)
        {
            for (int i = 0; i < n / 2; ++i)
            {
                // s[i] = '(' + s[i] + ',' + s[s.size() - i - 1] + ')';
                s[i] = '(' + s[i] + ',' + s[n - i - 1] + ')';
            }
            n /= 2;
        }
        return s[0];
    }
};